package com.faiz.algorithm;

import java.util.Deque;
import java.util.LinkedList;

public class Trap {
    public int trap(int[] height) {
        int l = height.length;
        if (l <= 0) {
            return 0;
        }
        //使用模拟括号匹配的方法
        int res = 0;
        Deque<Integer> stack = new LinkedList<>();
        int i = 0;
        while (i < l) {
            if (stack.isEmpty() || stack.peek() >= height[i]) {
                stack.push(height[i]);
                i++;
            } else {
                int count = 0;
                int pop = stack.peek();
                while (!stack.isEmpty() && stack.peek() <= pop) {
                    count++;
                    pop = stack.pop();
                }
                if (!stack.isEmpty()) {
                    res += count * (Math.min(height[i], stack.peek()) - pop);
                }
                stack.push(height[i]);
                i++;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        Trap trap = new Trap();
        System.out.println(trap.trap(nums));
    }
}
